Turing Machine
Q11.
Define languages L0 and L1 as follows : L0 = {< M, w, 0 > | M halts on w} L1 = {< M, w, 1 > | M does not halts on w} Here < M, w, i > is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let L=L0 \cup L1. Which of the following is true ?Q12.
Consider the following problem x . Given a Turing machine M over the input alphabet \Sigma, any state q of M. And a word w \in \Sigma *) does the computation of M on w visit the state q ? Which of the following statements about x is correct ?Q13.
A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?